/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// 二叉搜索树中序遍历一定递增
// 并且只用保证当前访问的节点的值 比前一个大就行
// 所以需要用一个指针指向前一个
// 我这里用的temp
var isValidBST = function (root) {
  let flag = true
  let temp = Number.MIN_SAFE_INTEGER
  const dfs = (tnode) => {
    if (tnode.left) dfs(tnode.left)
    if (tnode.val > temp) {
      temp = tnode.val
    } else {
      flag = false
      return
    }
    if (tnode.right) dfs(tnode.right)
  }
  dfs(root)
  return flag
};
// 中序遍历修改一下，如何从递归中直接返回结果？
var isValidBST = function (root) {
  let temp = Number.MIN_SAFE_INTEGER
  const dfs = (tnode) => {
    if(tnode === null) return true
    // 左子树不满足条件或者当前值比前一个值更小
    if(!dfs(tnode.left) || tnode.val <= temp) return false
    temp = tnode.val
    return dfs(tnode.right)
  }
  return dfs(root)
};
// 前序遍历也可以学习一下
// left和right是左右边界
// 前序遍历的第一个也就是根节点的取值假设为x，那么它左边的第一个节点，的取值就是(-Infinity, x) 右边(x, Infinity)
// 此后依据这个往下走
// 初始化的时候，x的取值范围为(-Infinity, Infinity)
var isValidBST = function (root, left = Number.MIN_SAFE_INTEGER, right = Number.MAX_SAFE_INTEGER) {
  if(root == null) return true
  let x = root.val
  return left < x && right > x && isValidBST(root.left, left, x) && isValidBST(root.right, x, right)
};